//
// (C) Copyright 2009 Irantha Suwandarathna (irantha@gmail.com)
// All rights reserved.
//

/* Copyright (c) 1995-2000, The Hypersonic SQL Group.
 * All rights reserved.
 *
 * Redistribution and use _in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * Redistributions of source code must retain the above copyright notice, this
 * list of conditions and the following disclaimer.
 *
 * Redistributions _in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer _in the documentation
 * and/or other materials provided with the distribution.
 *
 * Neither the name of the Hypersonic SQL Group nor the names of its
 * contributors may be used to endorse or promote products derived from this
 * software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE HYPERSONIC SQL GROUP,
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * This software consists of voluntary contributions made by many individuals
 * on behalf of the Hypersonic SQL Group.
 *
 *
 * For work added by the HSQL Development Group:
 *
 * Copyright (c) 2001-2008, The HSQL Development Group
 * All rights reserved.
 *
 * Redistribution and use _in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * Redistributions of source code must retain the above copyright notice, this
 * list of conditions and the following disclaimer.
 *
 * Redistributions _in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer _in the documentation
 * and/or other materials provided with the distribution.
 *
 * Neither the name of the HSQL Development Group nor the names of its
 * contributors may be used to endorse or promote products derived from this
 * software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */


using System;
using System.Collections.Generic;
using System.Text;
using System.Threading;
using EffiProz.Core.Lib;
using EffiProz.Core.Persist;
using EffiProz.Core.Rights;
using EffiProz.Core.Errors;
using EffiProz.Core.DataTypes;
using EffiProz.Core.Navigators;


namespace EffiProz.Core.Indexes
{
    // fredt@users 20020221 - patch 513005 by sqlbob@users - corrections
    // fredt@users 20020225 - patch 1.7.0 - changes to support cascading deletes
    // tony_lai@users 20020820 - patch 595052 - better error message
    // fredt@users 20021205 - patch 1.7.2 - changes to method signature
    // fredt@users - patch 1.80 - reworked the interface and comparison methods

    /**
    * Implementation of an AVL tree with parent pointers in nodes. Subclasses
    * of Node implement the tree node objects for memory or disk storage. An
    * Index has a root Node that is linked with other nodes using Java Object
    * references or file pointers, depending on Node implementation.<p>
    * An Index object also holds information on table columns (in the form of int
    * indexes) that are covered by it.<p>
    *
    *  New class derived from Hypersonic SQL code and enhanced in HSQLDB. <p>
    *
    * @author Thomas Mueller (Hypersonic SQL Group)
    * @author Fred Toussi (fredt@users dot sourceforge.net)
    * @version 1.9.0
    * @since Hypersonic SQL
    */
    public class IndexAVL : Index
    {
        // types of index
        public const int MEMORY_INDEX  = 0;
        public const int DISK_INDEX = 1;
        public const int POINTER_INDEX = 2;

        // fields
        public long persistenceId;
        public QNameManager.QName name;
        public bool[] colCheck;
        public int[] colIndex;
        public int[] defaultColMap;
        public SqlType[] colTypes;
        public bool[] colDesc;
        public bool[] nullsLast;
        public int[] pkCols;
        public SqlType[] pkTypes;
        public bool _isUnique;    // DDL uniqueness
        public bool useRowId;
        public bool _isConstraint;
        public bool _isForward;
        public int depth;
        public static IndexRowIterator _emptyIterator =
            new IndexRowIterator(null, (PersistentStore)null, null, null, false);
        private TableBase table;
        private int position;

#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
        ReaderWriterLockSlim _lock = new ReaderWriterLockSlim(LockRecursionPolicy.SupportsRecursion);
#else
        private class Dummy { };
        Object _lock = new Dummy();
#endif


        //
        public static Index[] emptyArray = new IndexAVL[] { };


        //Dummy Root
        public NodeAVL root = null;
        /**
         * Set a node as child of another
         *
         * @param x parent node
         * @param isleft bool
         * @param n child node
         *
         */
        private static NodeAVL set(PersistentStore store, NodeAVL x,
                                   bool isleft, NodeAVL n)
        {

            if (isleft)
            {
                x = x.setLeft(store, n);
            }
            else
            {
                x = x.setRight(store, n);
            }

            if (n != null)
            {
                n.setParent(store, x);
            }

            return x;
        }

        /**
         * Returns either child node
         *
         * @param x node
         * @param isleft bool
         *
         * @return child node
         *
         */
        private static NodeAVL child(PersistentStore store, NodeAVL x,
                                     bool isleft)
        {
            return isleft ? x.getLeft(store)
                          : x.getRight(store);
        }

        private static void getColumnList(Table t, int[] col, int len,
                                          StringBuilder a)
        {
            a.Append('(');

            for (int i = 0; i < len; i++)
            {
                a.Append(t.getColumn(col[i]).columnName.statementName);

                if (i < len - 1)
                {
                    a.Append(',');
                }
            }
            a.Append(')');
        }

        /**
         * compares two full table rows based on a set of columns
         *
         * @param a a full row
         * @param b a full row
         * @param cols array of column indexes to compare
         * @param coltypes array of column types for the full row
         *
         * @return comparison result, -1,0,+1
         */
        public static int compareRows(Session session, Object[] a, Object[] b,
                                      int[] cols, SqlType[] coltypes)
        {

            int fieldcount = cols.Length;

            for (int j = 0; j < fieldcount; j++)
            {
                int i = coltypes[cols[j]].compare(session, a[cols[j]], b[cols[j]]);

                if (i != 0)
                {
                    return i;
                }
            }

            return 0;
        }

        /**
         * Constructor declaration
         *
         * @param name QNameManager.QName of the index
         * @param id persistnece id
         * @param table table of the index
         * @param columns array of column indexes
         * @param descending bool[]
         * @param nullsLast bool[]
         * @param colTypes array of column types
         * @param unique is this a unique index
         * @param constraint does this index belonging to a constraint
         * @param forward is this an auto-index for an FK that refers to a table
         *   defined after this table
         */
      
        public IndexAVL(QNameManager.QName name, long id, TableBase table, int[] columns,
                        bool[] descending, bool[] nullsLast,
                        SqlType[] colTypes, bool pk, bool unique,
                        bool constraint, bool forward)
        {

            persistenceId = id;
            this.name = name;
            this.colIndex = columns;
            this.colTypes = colTypes;
            this.colDesc = descending == null ? new bool[columns.Length]
                                                : descending;
            this.nullsLast = nullsLast == null ? new bool[columns.Length]
                                               : nullsLast;
            _isUnique = unique;
            _isConstraint = constraint;
            _isForward = forward;
            this.table = table;
            this.pkCols = table.getPrimaryKey();
            this.pkTypes = table.getPrimaryKeyTypes();
            useRowId = (!_isUnique && pkCols.Length == 0) || (colIndex.Length == 0);
            colCheck = table.getNewColumnCheckList();

            ArrayUtil.intIndexesToboolArray(colIndex, colCheck);

            defaultColMap = new int[columns.Length];

            ArrayUtil.fillSequence(defaultColMap);
        }

        // SchemaObject implementation
        public int getType()
        {
            return SchemaObjectTypes.INDEX;
        }

        public QNameManager.QName getName()
        {
            return name;
        }

        public QNameManager.QName getCatalogName()
        {
            return name.schema.schema;
        }

        public QNameManager.QName getSchemaName()
        {
            return name.schema;
        }

        public Grantee getOwner()
        {
            return name.schema.owner;
        }

        public OrderedHashSet getReferences()
        {
            return new OrderedHashSet();
        }

        public OrderedHashSet getComponents()
        {
            return null;
        }

        public void compile(Session session, SchemaObject parentObject) { }

        public String getSQL()
        {

            StringBuilder sb = new StringBuilder();

            sb = new StringBuilder(64);

            sb.Append(Tokens.T_CREATE).Append(' ');

            if (isUnique())
            {
                sb.Append(Tokens.T_UNIQUE).Append(' ');
            }

            sb.Append(Tokens.T_INDEX).Append(' ');
            sb.Append(getName().statementName);
            sb.Append(' ').Append(Tokens.T_ON).Append(' ');
            sb.Append(((Table)table).getName().getSchemaQualifiedStatementName());

            int[] col = getColumns();
            int len = getVisibleColumns();

            getColumnList(((Table)table), col, len, sb);

            return sb.ToString();
        }

        // IndexInterface
        public RowIterator emptyIterator()
        {
            return _emptyIterator;
        }

        public int getPosition()
        {
            return position;
        }

        public void setPosition(int position)
        {
            this.position = position;
        }

        public long getPersistenceId()
        {
            return persistenceId;
        }

        /**
         * Returns the count of visible columns used
         */
        public int getVisibleColumns()
        {
            return colIndex.Length;
        }

        /**
         * Returns the count of visible columns used
         */
        public int getColumnCount()
        {
            return colIndex.Length;
        }

        /**
         * Is this a UNIQUE index?
         */
        public bool isUnique()
        {
            return _isUnique;
        }

        /**
         * Does this index belong to a constraint?
         */
        public bool isConstraint()
        {
            return _isConstraint;
        }

        /**
         * Returns the array containing column indexes for index
         */
        public int[] getColumns()
        {
            return colIndex;
        }

        /**
         * Returns the array containing column indexes for index
         */
        public SqlType[] getColumnTypes()
        {
            return colTypes;
        }

        public bool[] getColumnDesc()
        {
            return colDesc;
        }

        /**
         * Returns a value indicating the order of different types of index in
         * the list of indexes for a table. The position of the groups of Indexes
         * in the list in ascending order is as follows:
         *
         * primary key index
         * unique constraint indexes
         * autogenerated foreign key indexes for FK's that reference this table or
         *  tables created before this table
         * user created indexes (CREATE INDEX)
         * autogenerated foreign key indexes for FK's that reference tables created
         *  after this table
         *
         * Among a group of indexes, the order is based on the order of creation
         * of the index.
         *
         * @return ordinal value
         */
        public int getIndexOrderValue()
        {

            if (_isConstraint)
            {
                return _isForward ? 4
                                 : _isUnique ? 0
                                            : 1;
            }
            else
            {
                return 2;
            }
        }

        public bool isForward()
        {
            return _isForward;
        }

        /**
         * Returns the node count.
         */
        public int size(PersistentStore store)
        {

            int count = 0;

#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
               _lock.EnterReadLock();
#else
            Monitor.Enter(_lock);
#endif

            try
            {
                RowIterator it = firstRow(null, store);

                while (it.hasNext())
                {
                    it.getNextRow();

                    count++;
                }

                return count;
            }
            finally
            {

#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
               _lock.ExitReadLock();
#else
                Monitor.Exit(_lock);
#endif
           
            }
        }

        public int sizeEstimate(PersistentStore store)
        {
            return (int)(1L << depth);
        }

        public bool isEmpty(PersistentStore store)
        {

#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
               _lock.EnterReadLock();
#else
            Monitor.Enter(_lock);
#endif

            try
            {
                return getAccessor(store) == null;
            }
            finally
            {

#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
               _lock.ExitReadLock();
#else
                Monitor.Exit(_lock);
#endif
            }
        }

        public void checkIndex(PersistentStore store)
        {


#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
               _lock.EnterReadLock();
#else
            Monitor.Enter(_lock);
#endif

            try
            {
                NodeAVL p = getAccessor(store);
                NodeAVL f = null;

                while (p != null)
                {
                    f = p;

                    checkNodes(store, p);

                    p = p.getLeft(store);
                }

                p = f;

                while (f != null)
                {
                    checkNodes(store, f);

                    f = next(store, f);
                }
            }
            finally
            {
#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
               _lock.ExitReadLock();
#else
                Monitor.Exit(_lock);
#endif
            }
        }

        private void checkNodes(PersistentStore store, NodeAVL p)
        {

            NodeAVL l = p.getLeft(store);
            NodeAVL r = p.getRight(store);
#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
            if (l != null && l.getBalance(store) == -2)
            {
                System.Diagnostics.Debug.Write("broken index - deleted");
            }

            if (r != null && r.getBalance(store) == -2)
            {
                System.Diagnostics.Debug.Write("broken index -deleted");
            }

            if (l != null && !p.Equals(l.getParent(store)))
            {
                System.Diagnostics.Debug.Write("broken index - no parent");
            }

            if (r != null && !p.Equals(r.getParent(store)))
            {
                System.Diagnostics.Debug.Write("broken index - no parent");
            }
#endif
        }

        /**
         * Insert a node into the index
         */
        public  void insert(Session session, PersistentStore store, Row row)
        {

            NodeAVL n;
            NodeAVL x;
            bool isleft = true;
            int compare = -1;

#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
               _lock.EnterWriteLock();
#else
            Monitor.Enter(_lock);
#endif
            store.lockStore();

            try
            {
                n = getAccessor(store);
                x = n;

                if (n == null)
                {
                    store.setAccessor(this, ((RowAVL)row).getNode(position));

                    return;
                }

                while (true)
                {
                    Row currentRow = n.getRow(store);

                    compare = compareRowForInsertOrDelete(session, row,
                                                          currentRow);

                    if (compare == 0)
                    {
                        throw Error.error(ErrorCode.X_23505);
                    }

                    isleft = compare < 0;
                    x = n;
                    n = child(store, x, isleft);

                    if (n == null)
                    {
                        break;
                    }
                }

                x = x.set(store, isleft, ((RowAVL)row).getNode(position));

                balance(store, x, isleft);
            }
            finally
            {
                store.unlockStore();

#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
               _lock.ExitWriteLock();
#else
                Monitor.Exit(_lock);
#endif

            }
        }

        public void delete(PersistentStore store, Row row)
        {

            if (!row.isInMemory())
            {
                row = (Row)store.get(row, false);
            }

            NodeAVL node = ((RowAVL)row).getNode(position);

            delete(store, node);
        }

        public void delete(PersistentStore store, NodeAVL x)
        {

            if (x == null)
            {
                return;
            }

            NodeAVL n;

#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
               _lock.EnterWriteLock();
#else
            Monitor.Enter(_lock);
#endif
            store.lockStore();

            try
            {
                if (x.getLeft(store) == null)
                {
                    n = x.getRight(store);
                }
                else if (x.getRight(store) == null)
                {
                    n = x.getLeft(store);
                }
                else
                {
                    NodeAVL d = x;

                    x = x.getLeft(store);

                    while (true)
                    {
                        NodeAVL temp = x.getRight(store);

                        if (temp == null)
                        {
                            break;
                        }

                        x = temp;
                    }

                    // x will be replaced with n later
                    n = x.getLeft(store);

                    // swap d and x
                    int b = x.getBalance(store);

                    x = x.setBalance(store, d.getBalance(store));
                    d = d.setBalance(store, b);

                    // set x.parent
                    NodeAVL xp = x.getParent(store);
                    NodeAVL dp = d.getParent(store);

                    if (d.isRoot(store))
                    {
                        store.setAccessor(this, x);
                    }

                    x = x.setParent(store, dp);

                    if (dp != null)
                    {
                        if (dp.isRight(d))
                        {
                            dp = dp.setRight(store, x);
                        }
                        else
                        {
                            dp = dp.setLeft(store, x);
                        }
                    }

                    // relink d.parent, x.left, x.right
                    if (d.Equals(xp))
                    {
                        d = d.setParent(store, x);

                        if (d.isLeft(x))
                        {
                            x = x.setLeft(store, d);

                            NodeAVL dr = d.getRight(store);

                            x = x.setRight(store, dr);
                        }
                        else
                        {
                            x = x.setRight(store, d);

                            NodeAVL dl = d.getLeft(store);

                            x = x.setLeft(store, dl);
                        }
                    }
                    else
                    {
                        d = d.setParent(store, xp);
                        xp = xp.setRight(store, d);

                        NodeAVL dl = d.getLeft(store);
                        NodeAVL dr = d.getRight(store);

                        x = x.setLeft(store, dl);
                        x = x.setRight(store, dr);
                    }

                    x.getRight(store).setParent(store, x);
                    x.getLeft(store).setParent(store, x);

                    // set d.left, d.right
                    d = d.setLeft(store, n);

                    if (n != null)
                    {
                        n = n.setParent(store, d);
                    }

                    d = d.setRight(store, null);
                    x = d;
                }

                bool isleft = x.isFromLeft(store);

                x.replace(store, this, n);

                n = x.getParent(store);

                x.delete();

                while (n != null)
                {
                    x = n;

                    int sign = isleft ? 1
                                      : -1;

                    switch (x.getBalance(store) * sign)
                    {

                        case -1:
                            x = x.setBalance(store, 0);
                            break;

                        case 0:
                            x = x.setBalance(store, sign);

                            return;

                        case 1:
                            NodeAVL r = child(store, x, !isleft);
                            int b = r.getBalance(store);

                            if (b * sign >= 0)
                            {
                                x.replace(store, this, r);

                                NodeAVL _child = child(store, r, isleft);

                                x = x.set(store, !isleft, _child);
                                r = r.set(store, isleft, x);

                                if (b == 0)
                                {
                                    x = x.setBalance(store, sign);
                                    r = r.setBalance(store, -sign);

                                    return;
                                }

                                x = x.setBalance(store, 0);
                                r = r.setBalance(store, 0);
                                x = r;
                            }
                            else
                            {
                                NodeAVL l = child(store, r, isleft);

                                x.replace(store, this, l);

                                b = l.getBalance(store);
                                r = r.set(store, isleft, child(store, l, !isleft));
                                l = l.set(store, !isleft, r);
                                x = x.set(store, !isleft, child(store, l, isleft));
                                l = l.set(store, isleft, x);
                                x = x.setBalance(store, (b == sign) ? -sign
                                                                    : 0);
                                r = r.setBalance(store, (b == -sign) ? sign
                                                                     : 0);
                                l = l.setBalance(store, 0);
                                x = l;
                            }
                            break;
                    }

                    isleft = x.isFromLeft(store);
                    n = x.getParent(store);
                }
            }
            finally
            {
                store.unlockStore();

#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
               _lock.ExitWriteLock();
#else
                Monitor.Exit(_lock);
#endif
            }
        }

        public bool exists(Session session, PersistentStore store,
                              Object[] rowdata, int[] rowColMap)
        {
            return findNode(session, store, rowdata, rowColMap, rowColMap.Length)
                   != null;
        }

        /**
         * Return the first node equal to the indexdata object. The rowdata has
         * the same column mapping as this index.
         *
         * @param session session object
         * @param store store object
         * @param rowdata array containing index column data
         * @param match count of columns to match
         * @return iterator
         */
        public RowIterator findFirstRow(Session session, PersistentStore store,
                                        Object[] rowdata, int match)
        {

            NodeAVL node = findNode(session, store, rowdata, defaultColMap, match);

            return getIterator(session, store, node, false);
        }

        /**
         * Return the first node equal to the rowdata object.
         * The rowdata has the same column mapping as this table.
         *
         * @param session session object
         * @param store store object
         * @param rowdata array containing table row data
         * @return iterator
         */
        public RowIterator findFirstRow(Session session, PersistentStore store,
                                        Object[] rowdata)
        {

            NodeAVL node = findNode(session, store, rowdata, colIndex,
                                    colIndex.Length);

            return getIterator(session, store, node, false);
        }

        /**
         * Return the first node equal to the rowdata object.
         * The rowdata has the column mapping privided in rowColMap.
         *
         * @param session session object
         * @param store store object
         * @param rowdata array containing table row data
         * @return iterator
         */
        public RowIterator findFirstRow(Session session, PersistentStore store,
                                        Object[] rowdata, int[] rowColMap)
        {

            NodeAVL node = findNode(session, store, rowdata, rowColMap,
                                    rowColMap.Length);

            return getIterator(session, store, node, false);
        }

        /**
         * Finds the first node that is larger or equal to the given one based
         * on the first column of the index only.
         *
         * @param session session object
         * @param store store object
         * @param value value to match
         * @param compare comparison Expression type
         *
         * @return iterator
         */
        public RowIterator findFirstRow(Session session, PersistentStore store,
                                        Object value, int compare)
        {

#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
               _lock.EnterReadLock();
#else
            Monitor.Enter(_lock);
#endif

            try
            {
                if (compare == OpTypes.SMALLER
                        || compare == OpTypes.SMALLER_EQUAL)
                {
                    return findFirstRowNotNull(session, store);
                }

                bool isEqual = compare == OpTypes.EQUAL
                                  || compare == OpTypes.IS_NULL;
                NodeAVL x = getAccessor(store);
                int iTest = 1;

                if (compare == OpTypes.GREATER)
                {
                    iTest = 0;
                }

                if (value == null && !isEqual)
                {
                    return _emptyIterator;
                }

                // this method returns the correct node only with the following conditions
                bool check = compare == OpTypes.GREATER
                                || compare == OpTypes.EQUAL
                                || compare == OpTypes.GREATER_EQUAL;

                if (!check)
                {
                    Error.runtimeError(ErrorCode.U_S0500, "IndexAVL");
                }

                while (x != null)
                {
                    bool t = colTypes[0].compare(
                   session, value, x.getData(store)[colIndex[0]]) >= iTest;

                    if (t)
                    {
                        NodeAVL r = x.getRight(store);

                        if (r == null)
                        {
                            break;
                        }

                        x = r;
                    }
                    else
                    {
                        NodeAVL l = x.getLeft(store);

                        if (l == null)
                        {
                            break;
                        }

                        x = l;
                    }
                }

                /*
                        while (x != null
                                && Column.compare(value, x.getData()[colIndex_0], colType_0)
                                   >= iTest) {
                            x = next(x);
                        }
                */
                while (x != null)
                {
                    Object colvalue = x.getData(store)[colIndex[0]];
                    int result = colTypes[0].compare(session, value, colvalue);

                    if (result >= iTest)
                    {
                        x = next(store, x);
                    }
                    else
                    {
                        if (isEqual)
                        {
                            if (result != 0)
                            {
                                x = null;
                            }
                        }
                        else if (colvalue == null)
                        {
                            x = next(store, x);

                            continue;
                        }

                        break;
                    }
                }

                // MVCC
                if (session == null || x == null)
                {
                    return getIterator(session, store, x, false);
                }

                while (x != null)
                {
                    Row row = x.getRow(store);

                    if (compare == OpTypes.EQUAL
                         && colTypes[0].compare(
                             session, value, row.getData()[colIndex[0]]) != 0)
                    {
                        x = null;

                        break;
                    }

                    if (session.database.txManager.canRead(session, row))
                    {
                        break;
                    }

                    x = next(store, x);
                }

                return getIterator(session, store, x,
                                   _isUnique && this.colIndex.Length == 1
                                   && compare == OpTypes.EQUAL);
            }
            finally
            {
#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
            _lock.ExitReadLock();
#else
                Monitor.Exit(_lock);
#endif
            }
        }

        /**
         * Finds the first node where the data is not null.
         *
         * @return iterator
         */
        public RowIterator findFirstRowNotNull(Session session,
                                               PersistentStore store)
        {

#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
            _lock.EnterReadLock();
#else
            Monitor.Enter(_lock);
#endif

            try
            {
                NodeAVL x = getAccessor(store);

                while (x != null)
                {
                    bool t = colTypes[0].compare(
                    session, null, x.getData(store)[colIndex[0]]) >= 0;

                    if (t)
                    {
                        NodeAVL r = x.getRight(store);

                        if (r == null)
                        {
                            break;
                        }

                        x = r;
                    }
                    else
                    {
                        NodeAVL l = x.getLeft(store);

                        if (l == null)
                        {
                            break;
                        }

                        x = l;
                    }
                }

                while (x != null)
                {
                    Object colvalue = x.getData(store)[colIndex[0]];

                    if (colvalue == null)
                    {
                        x = next(store, x);
                    }
                    else
                    {
                        break;
                    }
                }

                // MVCC
                while (session != null && x != null)
                {
                    Row row = x.getRow(store);

                    if (session.database.txManager.canRead(session, row))
                    {
                        break;
                    }

                    x = next(store, x);
                }

                return getIterator(session, store, x, false);
            }
            finally
            {

#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
            _lock.ExitReadLock();
#else
                Monitor.Exit(_lock);
#endif
            }
        }

        /**
         * Returns the row for the first node of the index
         *
         * @return Iterator for first row
         */
        public RowIterator firstRow(Session session, PersistentStore store)
        {

            int tempDepth = 0;

#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
               _lock.EnterReadLock();
#else
            Monitor.Enter(_lock);
#endif

            try
            {
                NodeAVL x = getAccessor(store);
                NodeAVL l = x;

                while (l != null)
                {
                    x = l;
                    l = x.getLeft(store);

                    tempDepth++;
                }

                while (session != null && x != null)
                {
                    Row row = x.getRow(store);

                    if (session.database.txManager.canRead(session, row))
                    {
                        break;
                    }

                    x = next(store, x);
                }

                return getIterator(session, store, x, false);
            }
            finally
            {
                depth = tempDepth;

#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
            _lock.ExitReadLock();
#else
                Monitor.Exit(_lock);
#endif
            }
        }

        public  RowIterator firstRow(PersistentStore store)
        {

            int tempDepth = 0;

#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
            _lock.EnterReadLock();
#else
            Monitor.Enter(_lock);
#endif

            try
            {
                NodeAVL x = getAccessor(store);
                NodeAVL l = x;

                while (l != null)
                {
                    x = l;
                    l = x.getLeft(store);

                    tempDepth++;
                }

                return getIterator(null, store, x, false);
            }
            finally
            {
                depth = tempDepth;

#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
            _lock.ExitReadLock();
#else
                Monitor.Exit(_lock);
#endif
            }
        }

        /**
         * Returns the row for the last node of the index
         *
         * @return last row
         */
        public Row lastRow(Session session, PersistentStore store)
        {

#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
               _lock.EnterReadLock();
#else
            Monitor.Enter(_lock);
#endif

            try
            {
                NodeAVL x = getAccessor(store);
                NodeAVL l = x;

                while (l != null)
                {
                    x = l;
                    l = x.getRight(store);
                }

                while (session != null && x != null)
                {
                    Row row = x.getRow(store);

                    if (session.database.txManager.canRead(session, row))
                    {
                        break;
                    }

                    x = last(store, x);
                }

                return x == null ? null
                                 : x.getRow(store);
            }
            finally
            {
#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
            _lock.ExitReadLock();
#else
                Monitor.Exit(_lock);
#endif
            }
        }

        /**
         * Returns the node after the given one
         *
         * @param x node
         *
         * @return next node
         */
        private NodeAVL next(Session session, PersistentStore store, NodeAVL x)
        {

            if (x == null)
            {
                return null;
            }

#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
            _lock.EnterReadLock();
#else
            Monitor.Enter(_lock);
#endif

            try
            {
                while (true)
                {
                    x = next(store, x);

                    if (x == null)
                    {
                        return x;
                    }

                    if (session == null)
                    {
                        return x;
                    }

                    Row row = x.getRow(store);

                    if (session.database.txManager.canRead(session, row))
                    {
                        return x;
                    }
                }
            }
            finally
            {
#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
            _lock.ExitReadLock();
#else
                Monitor.Exit(_lock);
#endif
            }
        }

        private NodeAVL next(PersistentStore store, NodeAVL x)
        {

            NodeAVL r = x.getRight(store);

            if (r != null)
            {
                x = r;

                NodeAVL l = x.getLeft(store);

                while (l != null)
                {
                    x = l;
                    l = x.getLeft(store);
                }

                return x;
            }

            NodeAVL ch = x;

            x = x.getParent(store);

            while (x != null && ch.Equals(x.getRight(store)))
            {
                ch = x;
                x = x.getParent(store);
            }

            return x;
        }

        private NodeAVL last(PersistentStore store, NodeAVL x)
        {

            if (x == null)
            {
                return null;
            }

#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
            _lock.EnterReadLock();
#else
            Monitor.Enter(_lock);
#endif

            try
            {
                NodeAVL left = x.getLeft(store);

                if (left != null)
                {
                    x = left;

                    NodeAVL right = x.getRight(store);

                    while (right != null)
                    {
                        x = right;
                        right = x.getRight(store);
                    }

                    return x;
                }

                NodeAVL ch = x;

                x = x.getParent(store);

                while (x != null && ch.Equals(x.getLeft(store)))
                {
                    ch = x;
                    x = x.getParent(store);
                }

                return x;
            }
            finally
            {
#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
            _lock.ExitReadLock();
#else
                Monitor.Exit(_lock);
#endif
            }
        }

        /**
         * Replace x with n
         *
         * @param x node
         * @param n node
         */
        private void replace(PersistentStore store, NodeAVL x, NodeAVL n)
        {

            if (x.isRoot(store))
            {
                if (n != null)
                {
                    n = n.setParent(store, null);
                }

                store.setAccessor(this, n);
            }
            else
            {
                x.getParent(store).set(store, x.isFromLeft(store), n);
            }
        }

        /**
         * Compares two table rows based on the columns of this index. The rowColMap
         * parameter specifies which columns of the other table are to be compared
         * with the colIndex columns of this index. The rowColMap can cover all
         * or only some columns of this index.
         *
         * @param a row from another table
         * @param rowColMap column indexes in the other table
         * @param b a full row in this table
         *
         * @return comparison result, -1,0,+1
         */
        public int compareRowNonUnique(Session session, Object[] a,
                                       int[] rowColMap, Object[] b)
        {

            int fieldcount = rowColMap.Length;

            for (int j = 0; j < fieldcount; j++)
            {
                int i = colTypes[j].compare(session, a[rowColMap[j]],
                                       b[colIndex[j]]);

                if (i != 0)
                {
                    return i;
                }
            }

            return 0;
        }

        public int compareRowNonUnique(Session session, Object[] a,
                                       int[] rowColMap, Object[] b,
                                       int fieldCount)
        {

            for (int j = 0; j < fieldCount; j++)
            {
                int i = colTypes[j].compare(session, a[rowColMap[j]],
                                       b[colIndex[j]]);

                if (i != 0)
                {
                    return i;
                }
            }

            return 0;
        }

        /**
         * As above but use the index column data
         */
        public int compareRowNonUnique(Session session, Object[] a, Object[] b,
                                       int fieldcount)
        {

            for (int j = 0; j < fieldcount; j++)
            {
                int i = colTypes[j].compare(session, a[j], b[colIndex[j]]);

                if (i != 0)
                {
                    return i;
                }
            }

            return 0;
        }

        /**
         * Compare two rows of the table for inserting rows into unique indexes
         * Supports descending columns.
         *
         * @param newRow data
         * @param existingRow data
         * @return comparison result, -1,0,+1
         */
        private int compareRowForInsertOrDelete(Session session, Row newRow,
                Row existingRow)
        {

            Object[] a = newRow.getData();
            Object[] b = existingRow.getData();
            int j = 0;
            bool hasNull = false;

            for (; j < colIndex.Length; j++)
            {
                Object currentvalue = a[colIndex[j]];
                Object othervalue = b[colIndex[j]];
                int i = colTypes[j].compare(session, currentvalue, othervalue);
                bool nulls = currentvalue == null || othervalue == null;

                if (i != 0)
                {
                    if (colDesc[j] && !nulls)
                    {
                        i = -i;
                    }

                    if (nullsLast[j] && nulls)
                    {
                        i = -i;
                    }

                    return i;
                }

                if (currentvalue == null)
                {
                    hasNull = true;
                }
            }

            if (_isUnique && !useRowId && !hasNull)
            {
                if (session == null
                        || session.database.txManager.canRead(session,
                            existingRow))
                {

                    //* debug 190
                    //                session.database.txManager.canRead(session, existingRow);
                    return 0;
                }
                else
                {
                    int difference = newRow.getPos() - existingRow.getPos();

                    return difference;
                }
            }

            for (j = 0; j < pkCols.Length; j++)
            {
                Object currentvalue = a[pkCols[j]];
                int i = pkTypes[j].compare(session, currentvalue, b[pkCols[j]]);

                if (i != 0)
                {
                    return i;
                }
            }

            if (useRowId)
            {
                int difference = newRow.getPos() - existingRow.getPos();

                if (difference < 0)
                {
                    difference = -1;
                }
                else if (difference > 0)
                {
                    difference = 1;
                }

                return difference;
            }

            if (session == null
                    || session.database.txManager.canRead(session, existingRow))
            {
                return 0;
            }
            else
            {
                int difference = newRow.getPos() - existingRow.getPos();

                if (difference < 0)
                {
                    difference = -1;
                }
                else if (difference > 0)
                {
                    difference = 1;
                }

                return difference;
            }
        }

        /**
         * Finds a match with a row from a different table
         *
         * @param rowdata array containing data for the index columns
         * @param rowColMap map of the data to columns
         * @param first true if the first matching node is required, false if any node
         * @return matching node or null
         */
        private NodeAVL findNode(Session session, PersistentStore store,
                                 Object[] rowdata, int[] rowColMap,
                                 int fieldCount)
        {


#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
               _lock.EnterReadLock();
#else
            Monitor.Enter(_lock);
#endif

            try
            {
                NodeAVL x = getAccessor(store);
                NodeAVL n;
                NodeAVL result = null;

                while (x != null)
                {
                    int i = this.compareRowNonUnique(session, rowdata, rowColMap,
                                                     x.getData(store),
                                                     fieldCount);

                    if (i == 0)
                    {
                        result = x;
                        n = x.getLeft(store);
                    }
                    else if (i > 0)
                    {
                        n = x.getRight(store);
                    }
                    else
                    {
                        n = x.getLeft(store);
                    }

                    if (n == null)
                    {
                        break;
                    }

                    x = n;
                }

                // MVCC 190
                if (session == null)
                {
                    return result;
                }

                while (result != null)
                {
                    Row row = result.getRow(store);

                    if (compareRowNonUnique(
                            session, rowdata, rowColMap, row.getData(),
                            fieldCount) != 0)
                    {
                        result = null;

                        break;
                    }

                    if (session.database.txManager.canRead(session, row))
                    {
                        break;
                    }

                    result = next(store, result);
                }

                return result;
            }
            finally
            {

#if !SILVERLIGHT && !PLATFORM_COMPACTFRAMEWORK
               _lock.ExitReadLock();
#else
                Monitor.Exit(_lock);
#endif
            }
        }

        /**
         * Balances part of the tree after an alteration to the index.
         */
        private void balance(PersistentStore store, NodeAVL x, bool isleft)
        {

            while (true)
            {
                int sign = isleft ? 1
                                  : -1;

                switch (x.getBalance(store) * sign)
                {

                    case 1:
                        x = x.setBalance(store, 0);

                        return;

                    case 0:
                        x = x.setBalance(store, -sign);
                        break;

                    case -1:
                        NodeAVL l = child(store, x, isleft);

                        if (l.getBalance(store) == -sign)
                        {
                            x.replace(store, this, l);

                            x = x.set(store, isleft, child(store, l, !isleft));
                            l = l.set(store, !isleft, x);
                            x = x.setBalance(store, 0);
                            l = l.setBalance(store, 0);
                        }
                        else
                        {
                            NodeAVL r = child(store, l, !isleft);

                            x.replace(store, this, r);

                            l = l.set(store, !isleft, child(store, r, isleft));
                            r = r.set(store, isleft, l);
                            x = x.set(store, isleft, child(store, r, !isleft));
                            r = r.set(store, !isleft, x);

                            int rb = r.getBalance(store);

                            x = x.setBalance(store, (rb == -sign) ? sign
                                                                  : 0);
                            l = l.setBalance(store, (rb == sign) ? -sign
                                                                 : 0);
                            r = r.setBalance(store, 0);
                        }

                        return;
                }

                if (x.isRoot(store))
                {
                    return;
                }

                isleft = x.isFromLeft(store);
                x = x.getParent(store);
            }
        }

        private NodeAVL getAccessor(PersistentStore store)
        {

            NodeAVL node = (NodeAVL)store.getAccessor(this);

            return node;
        }

        private IndexRowIterator getIterator(Session session,
                                             PersistentStore store, NodeAVL x,
                                             bool single)
        {

            if (x == null)
            {
                return _emptyIterator;
            }
            else
            {
                IndexRowIterator it = new IndexRowIterator(session, store, this,
                    x, single);

                return it;
            }
        }

        public sealed class IndexRowIterator : RowIterator
        {

            Session session;
            PersistentStore store;
            IndexAVL index;
            NodeAVL nextnode;
            Row lastrow;
            bool single;
            //IndexRowIterator last;
            //IndexRowIterator _next;
            //IndexRowIterator lastInSession;
            //IndexRowIterator nextInSession;

            /**
             * When session == null, rows from all sessions are returned
             */
            public IndexRowIterator(Session session, PersistentStore store,
                                    IndexAVL index, NodeAVL node, bool single)
            {

                this.session = session;
                this.store = store;
                this.index = index;
                this.single = single;

                if (index == null)
                {
                    return;
                }

                nextnode = node;
            }

            public bool hasNext()
            {
                return nextnode != null;
            }

            public Row getNextRow()
            {

                if (nextnode == null)
                {
                    release();

                    return null;
                }

                lastrow = nextnode.getRow(store);
                nextnode = single ? null
                                  : index.next(session, store, nextnode);

                return lastrow;
            }

            public void remove()
            {
                store.delete(lastrow);
                store.remove(lastrow.getPos());
            }

            public void release() { }

            public bool setRowColumns(bool[] columns)
            {
                return false;
            }

            public long getPos()
            {
                return nextnode.getPos();
            }
        }
//added
         public void setName(String _name, bool isquoted)  {
             name.rename(_name, isquoted);
         }

    }
}
